Fast Fourier Transformation; FFT

신호처리에서 시간 영역(time Domain)의 시간을 진폭으로 매핑하는 함수

FFT를 이용하면, 다항식 곱셈(일반적으로 \Theta(n^2)의 시간복잡도를 가짐)연산을

\Theata(nlg n)에 처리할 수 있다.

DFT & FFT

단위값의 복소수 근을 이용할 경우,

다항식의 계산과 보간법(점값표현->계수표현)을 \Theta(nlg n) 안에 처리 가능하다.

Discreted Fourier Transformation; DFT yk=A(wkn)=Σn−1j=0ajwkjn $y_k=A(w_n^k)=\Sigma_{j=0}^{n-1}a_jw_n^{kj}$ Fast Fourier Transforamtion; FFT 분할 정복 기법을 이용해 DFTn(a) $DFT_n(a)$ 를 Θ(nlgn) $\Theta(nlg n)$ 시간에 계산 A(x) $A(x)$ 를 짝수 인덱스 계수와 홀수 인덱스 계수 항으로 분할 A(x)=A[0](x2)+xA[1](x2) $A(x)=A^{[0]}(x^2)+xA^{[1]}(x^2)$

#include <iostream>

#include <vector>

#include <complex>

#include <cmath>

using namespace std;

vector<complex<double>> RecursiveFFT(vector<complex<double>> a){

int n=a.size();

if(n==1) return a;

complex<double> wn=exp(complex<double>(0, 2*M_PI/n));

complex<double> w0(1);

vector<complex<double>> a0;

vector<complex<double>> a1;

for(int i=0; i<n; i+=2){

a0.push_back(a[i]);

a1.push_back(a[i+1]);

}

if(!n%2) a0.push_back(a[n-1]);

vector<complex<double>> y0=RecursiveFFT(a0);

vector<complex<double>> y1=RecursiveFFT(a1);

vector<complex<double>> y(n);

for(int k=0; k<n/2; ++k){

y[k]=y0[k]+w0*y1[k];

y[k+n/2]=y0[k]-w0*y1[k];

w0*=wn;

}

return y;

}

int main(void){

vector<complex<double>> a={0, 1, 2, 3};

vector<complex<double>> DFT=RecursiveFFT(a);

for(int i=0; i<DFT.size(); ++i){

cout<<DFT[i]<<' ';

}

cout<<endl;

return 0;

}

보간법

점값 형태 -> 계수 형태

a=DFT−1n(y) $a=DFT^{-1}_n(y)$

Vander-monde 행렬의 역 행렬을 y에 곱함으로서 원래의 a를 얻을 수 있다.

FFT는 실제 신호처리에서 매우 빈번하게 사용되는 연산으로 연산의 속도가 매우 중요하다.

실제로 대부분의 컴퓨터에서는 Parallel FET 회로를 이용해 FFT를 병렬적으로 빠르게 연산하도록 지원한다.

Polynomial & Fast Fourier Transformation; FFT